/**
 * 剑指 Offer 16. 数值的整数次方
 * https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
 */

/**
 * @param {number} x
 * @param {number} n
 * @param {number[][]} cache
 * @param {number} end
 * @return {number}
 */
function resolve(x, n, cache, end) {
  while (cache[end][0] > n) {
    end -= 1;
  }
  const [multiple, value] = cache[end];
  const left = n % multiple;
  const count = (n - left) / multiple;
  let result = 1;
  for (let i = 0; i < count; i += 1) {
    result *= value;
  }
  if (left) {
    result *= resolve(x, left, cache, end - 1);
  }
  return result;
}

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
function myPow(x, n) {
  if (n === 0) {
    return 1;
  }
  if (n < 0) {
    n = -n;
    x = 1 / x;
  }
  const cache = [[0, 1], [1, x]];
  for (let i = 2; i <= n; i *= 2) {
    const [, value] = cache[cache.length - 1];
    cache.push([i, value * value]);
  }
  return resolve(x, n, cache, cache.length - 1);
}

console.log(myPow(2, 8) === 256);
console.log(myPow(2, 10) === 1024);
console.log(myPow(2.1, 3) === 9.261000000000001);
console.log(myPow(2, -2) === 0.25);
